package org.hot100_1;

import org.leetcode.TreeNode;

public class leetcode46 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if (preorder.length==0 || inorder.length==0){
            return null;
        }
        TreeNode root = helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return root;
    }

    private TreeNode helper(int [] preorder,int preStart,int preEnd,int [] inorder,int inStart , int inEnd){

        if (preStart>preEnd){
            return null;
        }

        int val = preorder[preStart];

        TreeNode root = new TreeNode(val);

        int midIndex =0;

        for (midIndex=inStart; midIndex <inEnd; midIndex++) {
            if (inorder[midIndex]==val){
                break;
            }
        }

        int inLeftStart = inStart;
        int inLeftEnd = midIndex-1;
        int leftLength = inLeftEnd-inLeftStart;

        int inRightStart = midIndex+1;
        int inRightEnd = inEnd;
        int rightLength = inRightEnd-inRightStart;

        int preLeftStart = preStart+1;
        int preLeftEnd = preLeftStart+leftLength;

        int preRightStart = preLeftEnd+1;
        int preRightEnd = preRightStart+rightLength;


        root.left=helper(preorder,preLeftStart,preLeftEnd,inorder,inLeftStart,inLeftEnd);

        root.right=helper(preorder,preRightStart,preRightEnd,inorder,inRightStart,inRightEnd);

        return root;

    }



}
